<head>
    <meta charset="UTF-8">
<title>历届试题 区间移位</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">【问题描述】</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">数轴上有</span><i><span lang="EN-US">n</span></i><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">个闭区间</span><i><span lang="EN-US">D</span></i><sub><span lang="EN-US">1</span></sub><span lang="EN-US">,</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">…</span><span lang="EN-US">,<i>D<sub>n</sub></i></span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">。其中区间</span><i><span lang="EN-US">D<sub>i</sub></span></i><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">用一对整数</span><span lang="EN-US">[<i>a<sub>i</sub></i>, <i>b<sub>i</sub></i>]</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">来描述，满足</span><i><span lang="EN-US">a<sub>i</sub></span></i><span lang="EN-US"> &lt; <i>b<sub>i</sub></i></span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">。已知这些区间的长度之和至少有</span><span lang="EN-US">10000</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">。所以，通过适当的移动这些区间，你总可以使得他们的“并”覆盖</span><span lang="EN-US">[0, 10000]</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">——也就是说</span><span lang="EN-US">[0, 10000]</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">这个区间内的每一个点都落于至少一个区间内。</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">你希望找一个移动方法，使得位移差最大的那个区间的位移量最小。</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">具体来说，假设你将</span><i><span lang="EN-US">D<sub>i</sub></span></i><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">移动到</span><span lang="EN-US">[<i>a<sub>i</sub></i>+<i>c<sub>i</sub></i>, <i>b<sub>i</sub></i>+<i>c<sub>i</sub></i>]</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">这个位置。你希望使得</span><span lang="EN-US">max<i><sub>i</sub></i> |<i>c<sub>i</sub></i>|
</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">最小。</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">【输入格式】</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">输入的第一行包含一个整数</span><span lang="EN-US">n</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">，表示区间的数量。</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">接下来有</span><span lang="EN-US">n</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">行，每行</span><span lang="EN-US">2</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">个整数</span><span lang="EN-US">a<sub>i</sub>,
b<sub>i</sub></span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">，以一个空格分开，表示区间</span><span lang="EN-US">[<i>a<sub>i</sub></i>, <i>b<sub>i</sub></i>]</span><span style="font-family:宋体;mso-ascii-font-family:
&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">。保证区间的长度之和至少是</span><span lang="EN-US">10000</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">。</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">【输出格式】</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">输出一个数，表示答案。如果答案是整数，只输出整数部分。如果答案不是整数，输出时四舍五入保留一位小数。</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">【样例输入】</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI1"><span lang="EN-US">2<o:p></o:p></span></p>

<p class="NOI1"><span lang="EN-US">10 5010<o:p></o:p></span></p>

<p class="NOI1"><span lang="EN-US">4980 9980<o:p></o:p></span></p>

<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">【样例输出】</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI1"><span lang="EN-US">20<o:p></o:p></span></p>

<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">【样例说明】</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">第一个区间往左移动</span><span lang="EN-US">10</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">；第二个区间往右移动</span><span lang="EN-US">20</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">。</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">【样例输入】</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI1"><span lang="EN-US">4<o:p></o:p></span></p>

<p class="NOI1"><span lang="EN-US">0 4000<o:p></o:p></span></p>

<p class="NOI1"><span lang="EN-US">3000 5000<o:p></o:p></span></p>

<p class="NOI1"><span lang="EN-US">5001 8000<o:p></o:p></span></p>

<p class="NOI1"><span lang="EN-US">7000 10000<o:p></o:p></span></p>

<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">【样例输出】</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI1"><span lang="EN-US">0.5<o:p></o:p></span></p>

<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">【样例说明】</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">第</span><span lang="EN-US">2</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">个区间往右移</span><span lang="EN-US">0.5</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">；第</span><span lang="EN-US">3</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">个区间往左移</span><span lang="EN-US">0.5</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">即可。</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI"><span style="font-family:黑体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">【数据规模与约定】</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">对于</span><span lang="EN-US">30%</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">的评测用例，</span><span lang="EN-US">1 ≤ <i>n</i> ≤ 10</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">；</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">对于</span><span lang="EN-US">100%</span><span style="font-family:
宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:&quot;Times New Roman&quot;">的评测用例，</span><span lang="EN-US">1 ≤ <i>n</i> ≤ 10000</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;mso-hansi-font-family:
&quot;Times New Roman&quot;">，</span><span lang="EN-US">0 ≤ <i>a<sub>i</sub></i> &lt; <i>b<sub>i</sub></i>
≤ 10000</span><span style="font-family:宋体;mso-ascii-font-family:&quot;Times New Roman&quot;;
mso-hansi-font-family:&quot;Times New Roman&quot;">。</span><span lang="EN-US"><o:p></o:p></span></p>

<p class="NOI0" style="margin-bottom:7.8pt;text-indent:24.0pt"><span lang="EN-US">&nbsp;</span></p>